package com.dyw.Day26;

/**
 * @author Devil
 * @create 2022-02-12 0:00
 *
 *
 * 环形链表
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
 *
 * 如果链表中存在环，则返回 true 。 否则，返回 false 。
 *
 * ps:这里的链表并非java jdk提供而是手动编写 没有那么多的方法
 *
 * 思路:快慢指针 理解为时针与秒针 因为速度的不同 总会相遇
 */
public class Demo01 {
    /**
     * 快慢指针 快指针每次走2补 慢指针每次走1步 只要满足m!=n即可
     * @param head
     * @return
     */
    public boolean hasCycle01(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //因为快指针要走两次的原因 必须要判断fast的下一个也不为空才行 否则fast.next为空了就没有next了 会报错
        while(fast!=null&&fast.next!=null){
            //快指针每次走2步
            fast=fast.next.next;
            //满指针每次走1步
            slow=slow.next;
            //如果快慢指针相与就有环 环形轨道上两个物体只要速度不同总会相遇
            if(fast==slow){
                return true;
            }
        }
        //如果fast==null 就代表无环 因为有环会无限进行下去
        return false;
    }

    /**
     * 根据环形链表一定无线循环的原理 我们根据题目定义的链表长度最大值 进行遍历链表 如果超过范围那么有环 否则无环
     * @param head
     * @return
     */
    public boolean hasCycle02(ListNode head){
        ListNode p = head;
        int count=0;
        while(p!=null){
            count++;
            p = p.next;
            if(count>=10000){
                return true;
            }
        }
        return false;
    }
}
